package linkedlist;

/**
 * @description: <a href="https://leetcode.cn/problems/merge-two-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj">21. 合并两个有序链表</a>
 * @author: zhaoyinglin
 * @date: 2024/3/5
 */
public class MergeTwoLists {

    public static void main(String[] args) {
        ListNode list1 = ListNode.generateLinkedList(new int[] { 1, 2, 4 });
        ListNode list2 = ListNode.generateLinkedList(new int[] { 1, 3, 4 });

        Solution solution = new Solution();
        ListNode mergeList = solution.mergeTwoLists(list1, list2);

        System.out.println(ListNode.toLinkedListString(list1));
        System.out.println(ListNode.toLinkedListString(list2));
        System.out.println(ListNode.toLinkedListString(mergeList));
    }

    static class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

            if (list1 == null && list2 == null) {
                return null;
            }
            if (list1 == null) {
                return list2;
            }
            if (list2 == null) {
                return list1;
            }

            ListNode p1 = list1, p2 = list2, merge = new ListNode(-1);

            ListNode head = merge;

            while (p1 != null && p2 != null) {

                int min;
                if (p1.val < p2.val) {
                    min = p1.val;
                    p1 = p1.next;
                } else {
                    min = p2.val;
                    p2 = p2.next;
                }
                merge.next = new ListNode(min);
                merge = merge.next;
            }

            while (p1 != null) {
                merge.next = new ListNode(p1.val);
                merge = merge.next;
                p1 = p1.next;
            }

            while (p2 != null) {
                merge.next = new ListNode(p2.val);
                merge = merge.next;
                p2 = p2.next;
            }

            return head.next;

        }
    }
}
